The NP-hard RAINBOW SUBGRAPH problem, motivated from bioinformatics, is\nto find in an edge-colored graph a subgraph that contains each edge color exactly once and\nhas at most k vertices. We examine the parameterized complexity of RAINBOW SUBGRAPH\nfor paths, trees, and general graphs. We show that RAINBOW SUBGRAPH is W[1]-hard with\nrespect to the parameter k and also with respect to the dual parameter := n ? k where n is\nthe number of vertices. Hence, we examine parameter combinations and show, for example,\na polynomial-size problem kernel for the combined parameter and ââ?¬Å?maximum number of\ncolors incident with any vertexââ?¬Â. Additionally, we show APX-hardness even if the input\ngraph is a properly edge-colored path in which every color occurs at most twice.
Loading....